package com.leetcode.根据数据结构分类.图;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/19
 * @description: 1584. 连接所有点的最小费用
 * https://leetcode-cn.com/problems/min-cost-to-connect-all-points/
 */
public class B_1584_连接所有点的最小费用 {

	public static void main(String[] args) {
		//int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
		int[][] points = {{2, -3}, {-17, -8}, {13, 8}, {-17, -15}};
		B_1584_连接所有点的最小费用 acion = new B_1584_连接所有点的最小费用();
		//int cost = acion.minCostConnectPointsByPrim(points);
		int cost = acion.minCostConnectPointsByKruskal(points);

		System.out.println("cost = " + cost);
	}

	/**
	 * 一开始以为是最短路径问题，后来才反应过来这是最小生成树
	 * （SP:一个顶点出发到其他顶点的最小的权重集合）
	 * （MST:最小的最大连接通量的权重和）
	 *
	 * @param points
	 * @return
	 */
	public int minCostConnectPoints(int[][] points) {
		return 0;
	}

	/**
	 * 通过 Kruskal 实现
	 * 1.计算两两之间边的距离，借助二叉堆；
	 * 2.循环弹出二叉堆元素，进行 isSame 判断-> false : union
	 * --
	 * 没想到 Kruskal 会比 Prim 更快一些！
	 *
	 * @param points
	 * @return
	 */
	public int minCostConnectPointsByKruskal(int[][] points) {
		int res = 0;
		int vertexSize = points.length;
		if (vertexSize <= 1) {
			return 0;
		}

		PriorityQueue<Edge> heap = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.value - o2.value;
			}
		});
		for (int i = 0; i < vertexSize; i++) {
			for (int j = i + 1; j < vertexSize; j++) {
				heap.offer(new Edge(i, j, getValue(points, i, j)));
			}
		}
		InnerUnionFind unionFind = new InnerUnionFind(vertexSize);
		Edge curEdge = heap.poll();
		//HashSet<Integer> vertexSet = new HashSet<>();
		//vertexSet.add(curEdge.from);
		//vertexSet.add(curEdge.to);
		int edgeSize = 1;
		res += curEdge.value;
		unionFind.union(curEdge.from, curEdge.to);
		int size = vertexSize - 1;
		while (edgeSize < size) {
			curEdge = heap.poll();
			while (unionFind.isSame(curEdge.from, curEdge.to)) {
				curEdge = heap.poll();
			}
			unionFind.union(curEdge.from, curEdge.to);
			edgeSize++;
			res += curEdge.value;
		}
		return res;
	}

	/**
	 * 通过 Prim() 实现
	 * 1.从 0 出发记录所有的边，放入 Set(Edge)
	 * 2.借助二叉堆，获取最小的 横切边
	 * --
	 * 但是借助 Edge 对象占据的内存太多了。可以优化一下
	 * --
	 * 看了一下题解，没想到还是通过借助一个 Edge 对象
	 *
	 * @param points
	 * @return
	 */
	public int minCostConnectPointsByPrim(int[][] points) {
		int res = 0;
		Set<Edge> edgeSet = new HashSet<>();
		//已经成为 MST 中的点 index
		Set<Integer> indexSet = new HashSet<>();
		//小顶堆
		PriorityQueue<Edge> heap = new PriorityQueue<>(new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.value - o2.value;
			}
		});
		int len = points.length;
		indexSet.add(0);
		int index = 0;
		//int[] curPoint = points[index];
		for (int i = 0; i < len; i++) {
			Edge edge = new Edge(index, i, getValue(points, index, i));
			edgeSet.add(edge);
			heap.offer(edge);
		}
		Edge minEdge;
		while (indexSet.size() < len) {
			minEdge = heap.poll();
			while (indexSet.contains(minEdge.to)) {
				minEdge = heap.poll();
			}

			res += minEdge.value;
			//记录
			indexSet.add(minEdge.to);
			index = minEdge.to;
			//再次计算 out degrees
			for (int i = 0; i < len; i++) {
				if (!indexSet.contains(i)) {
					Edge edge = new Edge(index, i, getValue(points, index, i));
					edgeSet.add(edge);
					heap.offer(edge);
				}
			}
		}
		return res;
	}

	/**
	 * 计算 index1 和 index2 顶点之间的距离
	 *
	 * @param points
	 * @param index1
	 * @param index2
	 * @return
	 */
	private Integer getValue(int[][] points, int index1, int index2) {
		return Math.abs(points[index1][0] - points[index2][0]) + Math.abs(points[index1][1] - points[index2][1]);
	}


	class Edge {
		/**
		 * 顶点的索引
		 * from - 开始
		 * to - 结束
		 */
		//Set<Integer> verteces = new HashSet<>();
		Integer from, to;

		/**
		 * 边的权重
		 */
		Integer value;

		public Edge(Integer index1, Integer index2, Integer value) {
			this.from = index1;
			this.to = index2;

			this.value = value;
		}
	}

	/**
	 * 并查集
	 */
	class InnerUnionFind {
		int[] parents;
		int[] ranks;

		public InnerUnionFind(int capacity) {
			parents = new int[capacity];
			ranks = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				parents[i] = i;
				ranks[i] = 1;
			}
		}

		/**
		 * 通过 index 找到根节点
		 *
		 * @param index
		 * @return
		 */
		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		/**
		 * 判断 index1 和 index2 是否是同个集合
		 *
		 * @param index1
		 * @param index2
		 * @return
		 */
		public boolean isSame(int index1, int index2) {
			return find(index1) == find(index2);
		}

		/**
		 * 合并
		 *
		 * @param index1
		 * @param index2
		 */
		public void union(int index1, int index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			if (ranks[p1] == ranks[p2]) {
				parents[p1] = parents[p2];
				ranks[p2]++;
			} else if (ranks[p1] < ranks[p2]) {
				parents[p1] = parents[p2];
			} else {
				parents[p2] = parents[p1];
			}
		}
	}
}

